Recent trends in software have shifted to programming in object oriented languages. Object oriented programming shifts the emphasis of software development away from function decomposition and towards the recognition of units of software called “objects” which encapsulate both data and functions. Object Oriented Programming (OOP) objects are software entities comprising data structures and operations on data. Together, these elements enable objects to model virtually any real-world entity in terms of its characteristics, represented by its data elements, and its behavior represented by its data manipulation functions.
The benefit of object technology arises out of three basic principles: encapsulation, polymorphism and inheritance. Objects hide or encapsulate the internal structure of their data and the algorithms by which their functions work. Instead of exposing these implementation details, objects present interfaces that represent their abstractions cleanly with no extraneous information. Polymorphism takes encapsulation one step further—the idea being many shapes, one interface. The third principle is inheritance, which allows developers to reuse pre-existing design and code. This capability allows developers to avoid creating software from scratch. Rather, through inheritance, developers derive subclasses that inherit behaviors which the developer then customizes to meet particular needs.
Certain object oriented programming languages (e.g., C++, C#, Java, COM) support a programming construct called an interface. An interface includes declarations of methods, constants and properties. The interfaces can be inherited or implemented by a class type. Classes can also implement one or more interfaces. Methods declared in an interface can only be implemented in a class, not in an interface. When a class implements an interface, it must implement every method in the interface and all other interfaces which the interface extends.
A class type can be converted to any of the interfaces it implements, with no change in the pointer referring to the class, only the compile-time type is affected. When a member function of an interface is called, a compiler, does not in general know the type of the underlying class type. Therefore, it cannot at compile time determine the address or virtual table slot within the class virtual table of the method to call. The interface call code generated by the compiler must locate the class method implementing the interface method at runtime. In the implementation of interfaces, there is typically a virtual table for each interface implemented by a class type. Therefore, the problem reduces to finding that virtual table for the actual runtime class type and calling through that virtual table using the known virtual slot number of the method called. This is referred to as an interface dispatch.
The general problem is reduced to implementing an efficient mechanism in both space and speed for performing an interface dispatch. Conventional solution include providing a number of look ups through secondary data structures. These solutions are slow and utilize a tremendous amount of memory in building tables. One possible solution is to have each class type contain a list of pairs (interface type, interface virtual table) for all the interface types that it implements, and to search that list at runtime whenever an interface call is made. This solution is slow for two reasons: first, because the search code is large enough that it can't reasonably be expanded inline, so there is overhead for an additional call to a helper function, second because the search is sequential. The second source of overhead can of course be addressed by fancier searching schemes—hashing, some sort of caching the entry last found, or moving popular entries to the front. Another solution is to search a compact data structure at the time of the call. Still, these schemes are likely to be much slower compared to a virtual call.
A faster solution is to assign an index to both class and interface types. To find a given interface associated with a class, a lookup is made in a rectangular matrix where the rows are indexed by class indices and the columns by interface indices. This solution uses a lot of memory because while there are many classes and interfaces, classes do not implement many interfaces, so the matrix will be quite sparse. Unused entries in the matrix will never be referenced by compiler-generated code. When classes and interfaces are loaded dynamically, the matrix would also have to be grown dynamically. Therefore, there is an unmet need in the art for a more efficient mechanism for interface dispatching.